{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Servers That Handled Most Number of Requests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #ordered-set #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #有序集合 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: busiestServers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到处理最多请求的服务器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>k</code>&nbsp;个服务器，编号为 <code>0</code>&nbsp;到 <code>k-1</code>&nbsp;，它们可以同时处理多个请求组。每个服务器有无穷的计算能力但是 <strong>不能同时处理超过一个请求</strong>&nbsp;。请求分配到服务器的规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第&nbsp;<code>i</code>&nbsp;（序号从 0 开始）个请求到达。</li>\n",
    "\t<li>如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。</li>\n",
    "\t<li>如果第&nbsp;<code>(i % k)</code>&nbsp;个服务器空闲，那么对应服务器会处理该请求。</li>\n",
    "\t<li>否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 <code>i</code>&nbsp;个服务器在忙，那么会查看第 <code>(i+1)</code>&nbsp;个服务器，第 <code>(i+2)</code>&nbsp;个服务器等等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个 <strong>严格递增</strong>&nbsp;的正整数数组&nbsp;<code>arrival</code>&nbsp;，表示第&nbsp;<code>i</code>&nbsp;个任务的到达时间，和另一个数组&nbsp;<code>load</code>&nbsp;，其中&nbsp;<code>load[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个请求的工作量（也就是服务器完成它所需要的时间）。你的任务是找到 <strong>最繁忙的服务器</strong>&nbsp;。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。</p>\n",
    "\n",
    "<p>请你返回包含所有&nbsp;<strong>最繁忙服务器</strong>&nbsp;序号的列表，你可以以任意顺序返回这个列表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/03/load-1.png\" style=\"height: 221px; width: 389px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] \n",
    "<strong>输出：</strong>[1] \n",
    "<strong>解释：</strong>\n",
    "所有服务器一开始都是空闲的。\n",
    "前 3 个请求分别由前 3 台服务器依次处理。\n",
    "请求 3 进来的时候，服务器 0 被占据，所以它被安排到下一台空闲的服务器，也就是服务器 1 。\n",
    "请求 4 进来的时候，由于所有服务器都被占据，该请求被舍弃。\n",
    "服务器 0 和 2 分别都处理了一个请求，服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, arrival = [1,2,3,4], load = [1,2,1,2]\n",
    "<strong>输出：</strong>[0]\n",
    "<strong>解释：</strong>\n",
    "前 3 个请求分别被前 3 个服务器处理。\n",
    "请求 3 进来，由于服务器 0 空闲，它被服务器 0 处理。\n",
    "服务器 0 处理了两个请求，服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, arrival = [1,2,3], load = [10,12,11]\n",
    "<strong>输出：</strong>[0,1,2]\n",
    "<strong>解释：</strong>每个服务器分别处理了一个请求，所以它们都是最忙的服务器。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 1, arrival = [1], load = [1]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arrival.length, load.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>arrival.length == load.length</code></li>\n",
    "\t<li><code>1 &lt;= arrival[i], load[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>arrival</code>&nbsp;保证 <strong>严格递增</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-servers-that-handled-most-number-of-requests](https://leetcode.cn/problems/find-servers-that-handled-most-number-of-requests/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-servers-that-handled-most-number-of-requests](https://leetcode.cn/problems/find-servers-that-handled-most-number-of-requests/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[1,2,3,4,5]\\n[5,2,3,3,3]', '3\\n[1,2,3,4]\\n[1,2,1,2]', '3\\n[1,2,3]\\n[10,12,11]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        from heapq import heappop, heappush\n",
    "        from sortedcontainers import SortedList\n",
    "        free = SortedList(range(k))\n",
    "        work = []\n",
    "        count = [0 for i in range(k)]\n",
    "        job = -1\n",
    "        for arrive, cost in zip(arrival, load):\n",
    "            job += 1\n",
    "            while work and work[0][0] <= arrive:\n",
    "                free.add(work[0][1])\n",
    "                heappop(work)\n",
    "            if len(free) == 0:\n",
    "                continue\n",
    "            index = free.bisect_left(job % k)\n",
    "            if index == len(free):\n",
    "                index = 0\n",
    "            index = free[index]\n",
    "            count[index] += 1\n",
    "            heappush(work, (arrive + cost, index))\n",
    "            free.remove(index)\n",
    "            \n",
    "        max_work = max(count)\n",
    "        return [i for i, req in enumerate(count) if req == max_work]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available=[i for i in range(k)]\n",
    "        busy=[]\n",
    "        c=[0]*k\n",
    "        n=len(arrival)\n",
    "        for i in range(n):\n",
    "            a=arrival[i]\n",
    "            l=load[i]\n",
    "            while busy and busy[0][0]<=a:\n",
    "                insort(available,busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available)==0:\n",
    "                continue\n",
    "            j=bisect_left(available,i%k)\n",
    "            if j==len(available):\n",
    "                j=0\n",
    "            now =available[j]\n",
    "            c[now]+=1\n",
    "            heappush(busy,(a+l,now))\n",
    "            available.remove(now)\n",
    "        maxRequest = max(c)\n",
    "        return [i for i, req in enumerate(c) if req == maxRequest]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        idle, using = list(range(k)), []\n",
    "        cnt = [0] * k\n",
    "\n",
    "        for i, (st, t) in enumerate(zip(arrival, load)):\n",
    "            while using and using[0][0] <= st:\n",
    "                _, idx = heappop(using)\n",
    "                heappush(idle, i + (idx - i) % k)\n",
    "            if idle:\n",
    "                idx = heappop(idle) % k\n",
    "                heappush(using, (st + t, idx))\n",
    "                cnt[idx] += 1\n",
    "\n",
    "        maxcnt = max(cnt)\n",
    "        ans = [i for i, req in enumerate(cnt) if req == maxcnt]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available=[i for i in range(k)]\n",
    "        busy=[]\n",
    "        c=[0]*k\n",
    "        n=len(arrival)\n",
    "        for i in range(n):\n",
    "            a=arrival[i]\n",
    "            l=load[i]\n",
    "            while busy and busy[0][0]<=a:\n",
    "                insort(available,busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available)==0:\n",
    "                continue\n",
    "            j=bisect_left(available,i%k)\n",
    "            if j==len(available):\n",
    "                j=0\n",
    "            now =available[j]\n",
    "            c[now]+=1\n",
    "            heappush(busy,(a+l,now))\n",
    "            available.pop(j)\n",
    "        maxRequest = max(c)\n",
    "        return [i for i, req in enumerate(c) if req == maxRequest]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available=[i for i in range(k)]\n",
    "        busy=[]\n",
    "        c=[0]*k\n",
    "        n=len(arrival)\n",
    "        for i in range(n):\n",
    "            a=arrival[i]\n",
    "            l=load[i]\n",
    "            while busy and busy[0][0]<=a:\n",
    "                insort(available,busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available)==0:\n",
    "                continue\n",
    "            j=bisect_left(available,i%k)\n",
    "            if j==len(available):\n",
    "                j=0\n",
    "            now =available[j]\n",
    "            c[now]+=1\n",
    "            heappush(busy,(a+l,now))\n",
    "            available.remove(now)\n",
    "        maxRequest = max(c)\n",
    "        return [i for i, req in enumerate(c) if req == maxRequest]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        busy = []\n",
    "        idle = list(range(k))\n",
    "        requests = [0] * k\n",
    "        import heapq\n",
    "        import bisect\n",
    "\n",
    "        for i in range(len(arrival)):\n",
    "            while busy and busy[0][0] <= arrival[i]:\n",
    "                _, server_id = heapq.heappop(busy)\n",
    "                bisect.insort(idle, server_id)\n",
    "            if idle:\n",
    "                index = bisect.bisect_left(idle, i%k)\n",
    "                if index == len(idle):\n",
    "                    index = 0\n",
    "                server_id = idle[index]\n",
    "                del idle[index]\n",
    "                requests[server_id] += 1\n",
    "                heapq.heappush(busy, (arrival[i] + load[i], server_id))\n",
    "\n",
    "        res = []\n",
    "        maxr = 0\n",
    "        for i in range(k):\n",
    "            if requests[i] > maxr:\n",
    "                res = [i]\n",
    "                maxr = requests[i]\n",
    "            elif requests[i] == maxr:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        busy = []\n",
    "        idle = list(range(k))\n",
    "        requests = [0] * k\n",
    "        import heapq\n",
    "        import bisect\n",
    "\n",
    "        for i in range(len(arrival)):\n",
    "            while busy and busy[0][0] <= arrival[i]:\n",
    "                _, server_id = heapq.heappop(busy)\n",
    "                bisect.insort(idle, server_id)\n",
    "            if idle:\n",
    "                index = bisect.bisect_left(idle, i%k)\n",
    "                if index == len(idle):\n",
    "                    index = 0\n",
    "                server_id = idle[index]\n",
    "                del idle[index]\n",
    "                requests[server_id] += 1\n",
    "                heapq.heappush(busy, (arrival[i] + load[i], server_id))\n",
    "\n",
    "        res = []\n",
    "        maxr = 0\n",
    "        for i in range(k):\n",
    "            if requests[i] > maxr:\n",
    "                res = [i]\n",
    "                maxr = requests[i]\n",
    "            elif requests[i] == maxr:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        # 用最小堆与有序集合，模拟\n",
    "        # 最小堆busy存放了正在执行任务的服务器的结束时间，以及服务器编号\n",
    "        # 当新任务到达时，如果busy不为空，判断堆顶的服务器结束时间是否小于新任务的到达时间\n",
    "        # 是的话就将堆顶服务器弹出并加入ava有序集合中，ava表示空闲的服务器\n",
    "        # 如果ava不为空，则可以执行新任务，找到第一个大于等于i%k的服务器，如果没有，则换成ava中编号最小的服务器执行\n",
    "        n = len(arrival)\n",
    "        task_num = [0]*k\n",
    "        ava = list(range(k))\n",
    "        busy = []\n",
    "        for i in range(n):\n",
    "            arr,length = arrival[i], load[i]\n",
    "            while busy and busy[0][0]<=arr:\n",
    "                ava.insert(bisect_left(ava, busy[0][1]),busy[0][1])\n",
    "                heapq.heappop(busy)\n",
    "            if not len(ava)==0:\n",
    "                idx = bisect_left(ava, i%k)\n",
    "                idx = 0 if idx == len(ava) else idx\n",
    "                heapq.heappush(busy, (arr+length, ava[idx]))\n",
    "                task_num[ava[idx]] += 1\n",
    "                ava.pop(idx)\n",
    "        pass\n",
    "\n",
    "        res = []\n",
    "        max_task = max(task_num)\n",
    "        for i in range(k):\n",
    "            if task_num[i] == max_task:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        # 使用一个优先队列来跟踪哪个服务器何时完成任务\n",
    "        working_servers = []\n",
    "        # 使用一个队列来跟踪当前可用的服务器\n",
    "        available_servers = list(range(k))\n",
    "        # 跟踪每个服务器处理的请求数量\n",
    "        server_count = [0] * k\n",
    "\n",
    "        for i, (a, l) in enumerate(zip(arrival, load)):\n",
    "            # 释放完成任务的服务器\n",
    "            while working_servers and working_servers[0][0] <= a:\n",
    "                _, server = heapq.heappop(working_servers)\n",
    "                available_servers.append(server)\n",
    "                available_servers.sort()  # 确保服务器是按正确的顺序排列的\n",
    "\n",
    "            if available_servers:\n",
    "                # 查找当前任务应该分配给哪个服务器\n",
    "                idx = i % k\n",
    "                server = None\n",
    "                if idx in available_servers:\n",
    "                    server = idx\n",
    "                    available_servers.remove(idx)\n",
    "                else:\n",
    "                    for s in available_servers:\n",
    "                        if s > idx:\n",
    "                            server = s\n",
    "                            available_servers.remove(s)\n",
    "                            break\n",
    "                    if server is None:\n",
    "                        server = available_servers.pop(0)\n",
    "\n",
    "                # 更新服务器的任务计数和工作队列\n",
    "                heapq.heappush(working_servers, (a + l, server))\n",
    "                server_count[server] += 1\n",
    "\n",
    "        # 找到处理最多任务的服务器的数量\n",
    "        max_count = max(server_count)\n",
    "        # 返回处理最多任务的所有服务器的列表\n",
    "        return [i for i, count in enumerate(server_count) if count == max_count]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available = list(range(k))\n",
    "        busy = [] \n",
    "        res = [0] * k\n",
    "        for i, a in enumerate(arrival):\n",
    "            while busy and busy[0][0] <= a:\n",
    "                _, x = heapq.heappop(busy)\n",
    "                heapq.heappush(available, i + (x - i) % k)\n",
    "\n",
    "            if available: \n",
    "                j = heapq.heappop(available) % k\n",
    "                heapq.heappush(busy, (a+load[i], j))\n",
    "                res[j] += 1\n",
    "\n",
    "        max_reqs = max(res)\n",
    "        return [i for i in range(k) if res[i] == max_reqs]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import heapq\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        task_num = [0]*k\n",
    "        # ava = SortedList(list(range(k)))\n",
    "        ava = list(range(k))\n",
    "        busy = []\n",
    "        for i in range(n):\n",
    "            arr,length = arrival[i], load[i]\n",
    "            while busy and busy[0][0]<=arr:\n",
    "                # ava.add(busy[0][1])\n",
    "                ava.insert(bisect_left(ava, busy[0][1]),busy[0][1])\n",
    "                heapq.heappop(busy)\n",
    "            if not len(ava)==0:\n",
    "                # idx = ava.bisect_left(i%k)\n",
    "                idx = bisect_left(ava, i%k)\n",
    "                idx = 0 if idx == len(ava) else idx\n",
    "                heapq.heappush(busy, (arr+length, ava[idx]))\n",
    "                task_num[ava[idx]] += 1\n",
    "                # ava.discard(ava[idx])\n",
    "                ava.pop(idx)\n",
    "        pass\n",
    "\n",
    "        res = []\n",
    "        max_task = max(task_num)\n",
    "        for i in range(k):\n",
    "            if task_num[i] == max_task:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        rec = [0] * k\n",
    "        n = len(load)\n",
    "        idle = SortedList(range(k))\n",
    "        free = []\n",
    "        for i, j in enumerate(arrival):\n",
    "            tar = i % k\n",
    "            while free and free[0][0] <= j:\n",
    "                a, b = heappop(free)\n",
    "                idle.add(b)\n",
    "            if not idle:\n",
    "                continue\n",
    "            idx = idle.bisect_left(tar)\n",
    "            if idx == len(idle):\n",
    "                using = idle[0]\n",
    "            else:\n",
    "                using = idle[idx]\n",
    "            idle.remove(using)\n",
    "            rec[using] += 1\n",
    "            heappush(free, [j + load[i], using])\n",
    "        mx = max(rec)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if rec[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        idls = SortedList(range(k))\n",
    "        using = []\n",
    "        cnt = [0] * k \n",
    "        for i, (st, end) in enumerate(zip(arrival, load)):\n",
    "            while using and using[0][0] <= st:\n",
    "                idls.add(using[0][1])\n",
    "                heappop(using)\n",
    "            if len(idls) == 0:\n",
    "                continue \n",
    "            j = idls.bisect_left(i % k)\n",
    "            if j == len(idls):\n",
    "                j = 0 \n",
    "            id = idls[j]\n",
    "            cnt[id] += 1\n",
    "            heappush(using, (st + end, id))\n",
    "            idls.remove(id)\n",
    "        max_cnt = max(cnt)\n",
    "        res = []\n",
    "        for i in range(len(cnt)):\n",
    "            if cnt[i] == max_cnt:\n",
    "                res.append(i)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \r\n",
    "class Solution:\r\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\r\n",
    "        idls = SortedList(range(k))\r\n",
    "        using = []\r\n",
    "        cnt = [0] * k \r\n",
    "        for i, (st, end) in enumerate(zip(arrival, load)):\r\n",
    "            while using and using[0][0] <= st:\r\n",
    "                idls.add(using[0][1])\r\n",
    "                heappop(using)\r\n",
    "\r\n",
    "            if len(idls) == 0:\r\n",
    "                continue\r\n",
    "            j = idls.bisect_left(i % k)\r\n",
    "            if j == len(idls):\r\n",
    "                j = 0 \r\n",
    "            id = idls[j]\r\n",
    "            cnt[id] += 1\r\n",
    "            heappush(using, (st + end, id))\r\n",
    "            idls.remove(id)\r\n",
    "        mx = max(cnt)\r\n",
    "        res = []\r\n",
    "        for i, x in enumerate(cnt) :\r\n",
    "            if x == mx :\r\n",
    "                res.append(i)\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        cnt = [0] * k\n",
    "        ava = SortedList(range(k))\n",
    "        h = []\n",
    "        mx = 0\n",
    "        for i, (arv, t) in enumerate(zip(arrival, load)):\n",
    "            while h and h[0][0] <= arv:\n",
    "                ava.add(h[0][1])\n",
    "                heappop(h)\n",
    "            \n",
    "            if len(ava) == 0: continue\n",
    "            j = ava.bisect_left(i % k)\n",
    "            if j == len(ava): j = 0\n",
    "            idx = ava[j]\n",
    "            cnt[idx] += 1\n",
    "            heappush(h, (arv + t, idx))\n",
    "            ava.remove(idx)\n",
    "            mx = max(mx, cnt[idx])\n",
    "        \n",
    "        return [i for i, x in enumerate(cnt) if x == mx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        ans = [0]* k\n",
    "        available = SortedList(range(k))\n",
    "        mission_queue = []\n",
    "        i = 0\n",
    "        n = len(arrival)\n",
    "        while i<n:\n",
    "            start,end = arrival[i],arrival[i]+load[i]\n",
    "            while mission_queue and mission_queue[0][0] <= start:\n",
    "                available.add(mission_queue[0][1])\n",
    "                heapq.heappop(mission_queue)\n",
    "            if len(available) == 0:\n",
    "                i += 1\n",
    "                continue #无可用的机器\n",
    "            j = available.bisect_left(i%k)\n",
    "            if j == len(available):\n",
    "                j = 0 #从0 开始\n",
    "            mechine = available[j]\n",
    "            ans[mechine] += 1 #标记使用次数\n",
    "            heapq.heappush(mission_queue,(end,mechine))\n",
    "            available.remove(mechine)\n",
    "            i += 1\n",
    "        res = []\n",
    "        maxcnt = 0\n",
    "        # print(ans)\n",
    "        for i in range(k):\n",
    "            if ans[i]>maxcnt:\n",
    "                res = [i]\n",
    "                maxcnt = ans[i]\n",
    "            elif ans[i] == maxcnt:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        free=SortedList(list(range(k)))\n",
    "        busy=[]\n",
    "        res=[0]*k\n",
    "        for i,(a,l) in enumerate(zip(arrival,load)):\n",
    "            while busy and busy[0][0]<=a:\n",
    "                t,j=heappop(busy)\n",
    "                free.add(j)\n",
    "            \n",
    "            if free:\n",
    "                j=free.bisect_left(i%k)\n",
    "                if j==len(free):j=0\n",
    "                res[free[j]]+=1                \n",
    "                heappush(busy,(a+l,free[j]))\n",
    "                free.remove(free[j])\n",
    "        mx=max(res)\n",
    "        ans=[]\n",
    "        for i in range(k):\n",
    "            if res[i]==mx:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available = SortedList(range(k))\n",
    "        busy = []\n",
    "        requests = [0] * k\n",
    "        for i, (start, t) in enumerate(zip(arrival, load)):\n",
    "            while busy and busy[0][0] <= start:\n",
    "                available.add(busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available) == 0:\n",
    "                continue\n",
    "            j = available.bisect_left(i % k)\n",
    "            if j == len(available):\n",
    "                j = 0\n",
    "            id = available[j]\n",
    "            requests[id] += 1\n",
    "            heappush(busy, (start + t, id))\n",
    "            available.remove(id)\n",
    "        maxRequest = max(requests)\n",
    "        return [i for i, req in enumerate(requests) if req == maxRequest]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        rec = [0] * k\n",
    "        n = len(load)\n",
    "        # if k >= n:\n",
    "        #     return [i for i in range(n)]\n",
    "        idle = SortedList(range(k))\n",
    "        free = []\n",
    "        for i, j in enumerate(arrival):\n",
    "            tar = i % k\n",
    "            while free and free[0][0] <= j:\n",
    "                a, b = heappop(free)\n",
    "                idle.add(b)\n",
    "            if not idle:\n",
    "                continue\n",
    "            idx = idle.bisect_left(tar)\n",
    "            if idx == len(idle):\n",
    "                using = idle[0]\n",
    "            else:\n",
    "                using = idle[idx]\n",
    "            idle.remove(using)\n",
    "            rec[using] += 1\n",
    "            heappush(free, [j + load[i], using])\n",
    "        mx = max(rec)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if rec[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available = SortedList(range(k))\n",
    "        busy = []\n",
    "        requests = [0] * k\n",
    "        for i, (start, t) in enumerate(zip(arrival, load)):\n",
    "            while busy and busy[0][0] <= start:\n",
    "                available.add(busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available) == 0:\n",
    "                continue\n",
    "            j = available.bisect_left(i % k)\n",
    "            if j == len(available):\n",
    "                j = 0\n",
    "            id = available[j]\n",
    "            requests[id] += 1\n",
    "            heappush(busy, (start + t, id))\n",
    "            available.remove(id)\n",
    "        maxRequest = max(requests)\n",
    "        return [i for i, req in enumerate(requests) if req == maxRequest]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available = SortedList(range(k))\n",
    "        busy = []\n",
    "        requests = [0] * k\n",
    "        for i in range(len(arrival)):\n",
    "            ti = arrival[i]\n",
    "            duri = load[i]\n",
    "            while busy and  busy[0][0]<=ti:\n",
    "                _, ind = heapq.heappop(busy)\n",
    "                available.add(ind)\n",
    "            if len(available)==0:\n",
    "                continue\n",
    "            j = bisect_left(available,i%k)\n",
    "            # print(j,len(available))\n",
    "            if j==len(available):\n",
    "                j=0\n",
    "            requests[available[j]]+=1\n",
    "            heapq.heappush(busy,(ti+duri,available[j]))\n",
    "            available.remove(available[j])\n",
    "        ans = []\n",
    "        max_t = 0\n",
    "        for i in range(len(requests)):\n",
    "            if requests[i]>max_t:\n",
    "                ans=[i]\n",
    "                max_t=requests[i]\n",
    "            elif requests[i]==max_t:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import time\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from heapq import heappop, heappush\n",
    "class Solution:\n",
    " \n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        available = SortedList(range(k))\n",
    "        busy = []\n",
    "        requests = [0] * k\n",
    "        for i, (start, t) in enumerate(zip(arrival, load)):\n",
    "            while busy and busy[0][0] <= start:\n",
    "                available.add(busy[0][1])\n",
    "                heappop(busy)\n",
    "            if len(available) == 0:\n",
    "                continue\n",
    "            j = available.bisect_left(i % k)\n",
    "            if j == len(available):\n",
    "                j = 0\n",
    "            id = available[j]\n",
    "            requests[id] += 1\n",
    "            heappush(busy, (start + t, id))\n",
    "            available.remove(id)\n",
    "        maxRequest = max(requests)\n",
    "        return [i for i, req in enumerate(requests) if req == maxRequest]\n",
    " \n",
    "if __name__ == '__main__':\n",
    "    \n",
    "    sln = Solution()\n",
    "    \n",
    "    k = 3\n",
    "    arrival = [1,2,3,4,5]\n",
    "    load = [5,2,3,3,3] \n",
    "    print(sln.busiestServers(k, arrival, load))\n",
    "    \n",
    "    k = 3\n",
    "    arrival = [1,2,3,4]\n",
    "    load = [1,2,1,2]\n",
    "    print(sln.busiestServers(k, arrival, load))        \n",
    "    \n",
    "    k = 3\n",
    "    arrival = [1,2,3]\n",
    "    load = [10,12,11]\n",
    "    print(sln.busiestServers(k, arrival, load))\n",
    "    \n",
    "    k = 3\n",
    "    arrival = [1,2,3,4,8,9,10]\n",
    "    load = [5,2,10,3,1,2,2]\n",
    "    print(sln.busiestServers(k, arrival, load))\n",
    "    \n",
    "    k = 1\n",
    "    arrival = [1]\n",
    "    load = [1]\n",
    "    print(sln.busiestServers(k, arrival, load))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        task_num = [0]*k\n",
    "        ava = SortedList(list(range(k)))\n",
    "        busy = []\n",
    "        for i in range(n):\n",
    "            arr,length = arrival[i], load[i]\n",
    "            while busy and busy[0][0]<=arr:\n",
    "                ava.add(busy[0][1])\n",
    "                heapq.heappop(busy)\n",
    "            if not len(ava)==0:\n",
    "                idx = ava.bisect_left(i%k)\n",
    "                idx = 0 if idx == len(ava) else idx\n",
    "                heapq.heappush(busy, (arr+length, ava[idx]))\n",
    "                task_num[ava[idx]] += 1\n",
    "                ava.discard(ava[idx])\n",
    "        pass\n",
    "\n",
    "        res = []\n",
    "        max_task = max(task_num)\n",
    "        for i in range(k):\n",
    "            if task_num[i] == max_task:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        c = Counter()\n",
    "        little_heap = []\n",
    "        big_heap = []\n",
    "        t = 0\n",
    "        using = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(big_heap, i)\n",
    "        for i in range(len(arrival)):\n",
    "            if i % k == 0:\n",
    "                while little_heap:\n",
    "                    heapq.heappush(big_heap, heapq.heappop(little_heap))\n",
    "            t = arrival[i]\n",
    "            while using and using[0][0] <= t:\n",
    "                _, server = heapq.heappop(using)\n",
    "                if server >= i % k:\n",
    "                    heapq.heappush(big_heap, server)\n",
    "                else:\n",
    "                    heapq.heappush(little_heap, server)\n",
    "            if big_heap:\n",
    "                server = heapq.heappop(big_heap)\n",
    "                c[server] += 1\n",
    "                heapq.heappush(using, (t + load[i], server))\n",
    "            elif little_heap:\n",
    "                server = heapq.heappop(little_heap)\n",
    "                c[server] += 1\n",
    "                heapq.heappush(using, (t + load[i], server))\n",
    "            else:\n",
    "                continue\n",
    "        max_num = max(c.values())\n",
    "        res = []\n",
    "        for key, value in c.items():\n",
    "            if value == max_num:\n",
    "                res.append(key)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        \n",
    "        stack = []\n",
    "        no_used = SortedList(range(k))\n",
    "        cnts = Counter()\n",
    "        for i , (t , length) in enumerate(zip(arrival,load)):\n",
    "            while stack and stack[0][0] <= t:\n",
    "                x , j = heapq.heappop(stack)\n",
    "                no_used.add(j)\n",
    "            if not no_used:continue\n",
    "            n_t = t + length\n",
    "            idx = bisect.bisect_left(no_used,i%k)\n",
    "            if idx == len(no_used):\n",
    "                j = no_used[0]\n",
    "            else:\n",
    "                j = no_used[idx]\n",
    "            no_used.discard(j)\n",
    "            cnts[j] += 1\n",
    "            heapq.heappush(stack,(n_t,j))\n",
    "        ans = []\n",
    "        max_r = 0\n",
    "        for k , v in cnts.items():\n",
    "            if v > max_r:\n",
    "                ans = [k]\n",
    "                max_r = v\n",
    "            elif v == max_r:\n",
    "                ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        rec = [0] * k\n",
    "        n = len(load)\n",
    "        if k >= n:\n",
    "            return [i for i in range(n)]\n",
    "        idle = SortedList(range(k))\n",
    "        free = []\n",
    "        for i, j in enumerate(arrival):\n",
    "            tar = i % k\n",
    "            while free and free[0][0] <= j:\n",
    "                a, b = heappop(free)\n",
    "                idle.add(b)\n",
    "            if not idle:\n",
    "                continue\n",
    "            idx = idle.bisect_left(tar)\n",
    "            if idx == len(idle):\n",
    "                using = idle[0]\n",
    "            else:\n",
    "                using = idle[idx]\n",
    "            idle.remove(using)\n",
    "            rec[using] += 1\n",
    "            heappush(free, [j + load[i], using])\n",
    "        mx = max(rec)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if rec[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        busy, free = [], SortedList(range(k))\n",
    "        cnt = [0 for _ in range(k)]\n",
    "        for r, (a, l) in enumerate(zip(arrival, load)):\n",
    "            start, end = a, a + l\n",
    "            while busy and busy[0][0] <= start:\n",
    "                _, i = heappop(busy)\n",
    "                free.add(i)\n",
    "            if len(free) == 0:\n",
    "                continue\n",
    "            idx = free.bisect_left(r % k)\n",
    "            if idx == len(free):\n",
    "                idx = free.bisect_left(0)\n",
    "            cnt[free[idx]] += 1\n",
    "            heappush(busy, (end, free[idx]))\n",
    "            free.pop(idx)\n",
    "        cnt_max = max(cnt)\n",
    "        return [i for i in range(k) if cnt[i] == cnt_max]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        cnt = [0] * k\n",
    "        idle = SortedList([i for i in range(k)])\n",
    "        using = [] # (endTime, serverId)\n",
    "        n = len(arrival)\n",
    "\n",
    "        for i in range(n):\n",
    "            while using and using[0][0] <= arrival[i]:\n",
    "                idle.add(heappop(using)[1])\n",
    "            if len(idle) == 0:\n",
    "                continue\n",
    "            idx = idle.bisect_left(i % k) \n",
    "            if idx == len(idle):\n",
    "                idx = 0\n",
    "            serverId = idle[idx]\n",
    "            idle.remove(serverId)\n",
    "            heappush(using, (arrival[i]+load[i], serverId))\n",
    "            cnt[serverId] += 1\n",
    "        \n",
    "        # print(cnt)\n",
    "        res = []\n",
    "        maxUsage = max(cnt)\n",
    "        for i in range(k):\n",
    "            if cnt[i] == maxUsage:\n",
    "                res.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        rec = [0] * k\n",
    "        n = len(load)\n",
    "        if k >= n:\n",
    "            return [i for i in range(n)]\n",
    "        idle = SortedList(range(k))\n",
    "        free = []\n",
    "        for i, j in enumerate(arrival):\n",
    "            tar = i % k\n",
    "            while free and free[0][0] <= j:\n",
    "                a, b = heappop(free)\n",
    "                idle.add(b)\n",
    "            if not idle:\n",
    "                continue\n",
    "            idx = idle.bisect_left(tar)\n",
    "            if idx == len(idle):\n",
    "                using = idle[0]\n",
    "            else:\n",
    "                using = idle[idx]\n",
    "            idle.remove(using)\n",
    "            rec[using] += 1\n",
    "            heappush(free, [j + load[i], using])\n",
    "        mx = max(rec)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if rec[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param k:\n",
    "        :param arrival:\n",
    "        :param load:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        freelist = SortedList()\n",
    "        for i in range(k):\n",
    "            freelist.add(i)\n",
    "        busylist = SortedList(key=lambda x: x[0])\n",
    "        count_map = {}\n",
    "        for k1, v in enumerate(zip(arrival, load)):\n",
    "            cur_time, cur_load = v\n",
    "            while busylist and busylist[0][0] <= cur_time:\n",
    "                _, server = busylist.pop(0)\n",
    "                freelist.add(server)\n",
    "            if not freelist:\n",
    "                continue\n",
    "            server = freelist.bisect_left(k1 % (k))\n",
    "            if server >= len(freelist):\n",
    "                server = 0\n",
    "            server = freelist.pop(server)\n",
    "            busylist.add((cur_time + cur_load, server))\n",
    "            count_map[server] = count_map.get(server, 0) + 1\n",
    "        max_count = max(count_map.values())\n",
    "        ans = []\n",
    "        for i in count_map:\n",
    "            if count_map[i] == max_count:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param k:\n",
    "        :param arrival:\n",
    "        :param load:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        freelist = SortedList()\n",
    "        for i in range(k):\n",
    "            freelist.add(i)\n",
    "        busylist = SortedList(key=lambda x: x[0])\n",
    "        count_map = {}\n",
    "        max_count = 0\n",
    "        for k1, v in enumerate(zip(arrival, load)):\n",
    "            cur_time, cur_load = v\n",
    "            while busylist and busylist[0][0] <= cur_time:\n",
    "                _, server = busylist.pop(0)\n",
    "                freelist.add(server)\n",
    "            if not freelist:\n",
    "                continue\n",
    "            server = freelist.bisect_left(k1 % (k))\n",
    "            if server >= len(freelist):\n",
    "                server = 0\n",
    "            server = freelist.pop(server)\n",
    "            busylist.add((cur_time + cur_load, server))\n",
    "            count_map[server] = count_map.get(server, 0) + 1\n",
    "            max_count = max(max_count, count_map[server])\n",
    "\n",
    "        ans = []\n",
    "        for i in count_map:\n",
    "            if count_map[i] == max_count:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param k:\n",
    "        :param arrival:\n",
    "        :param load:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        freelist = SortedList()\n",
    "        for i in range(k):\n",
    "            freelist.add(i)\n",
    "        busylist = SortedList(key=lambda x: x[0])\n",
    "        count_map = {}\n",
    "        max_count = 0\n",
    "        for k1, v in enumerate(zip(arrival, load)):\n",
    "            cur_time, cur_load = v\n",
    "            while busylist and busylist[0][0] <= cur_time:\n",
    "                _, server = busylist.pop(0)\n",
    "                freelist.add(server)\n",
    "            if not freelist:\n",
    "                continue\n",
    "            server = freelist.bisect_left(k1 % (k))\n",
    "            if server >= len(freelist):\n",
    "                server = 0\n",
    "            server = freelist.pop(server)\n",
    "            busylist.add((cur_time + cur_load, server))\n",
    "            count_map[server] = count_map.get(server, 0) + 1\n",
    "            max_count = max(max_count, count_map[server])\n",
    "\n",
    "        ans = []\n",
    "        for i in count_map:\n",
    "            if count_map[i] == max_count:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.busiestServers(k=3, arrival=[1, 2, 3, 4, 8, 9, 10], load=[5, 2, 10, 3, 1, 2, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param k:\n",
    "        :param arrival:\n",
    "        :param load:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        freelist = SortedList()\n",
    "        for i in range(k):\n",
    "            freelist.add(i)\n",
    "        busylist = SortedList(key=lambda x: x[0])\n",
    "        count_map = {}\n",
    "        for k1, v in enumerate(zip(arrival, load)):\n",
    "            cur_time, cur_load = v\n",
    "            while busylist and busylist[0][0] <= cur_time:\n",
    "                _, server = busylist.pop(0)\n",
    "                freelist.add(server)\n",
    "            if not freelist:\n",
    "                continue\n",
    "            server = freelist.bisect_left(k1 % (k))\n",
    "            if server >= len(freelist):\n",
    "                server = 0\n",
    "            server = freelist.pop(server)\n",
    "            busylist.add((cur_time + cur_load, server))\n",
    "            count_map[server] = count_map.get(server, 0) + 1\n",
    "\n",
    "        max_count = max(count_map.values())\n",
    "        ans = []\n",
    "        for i in count_map:\n",
    "            if count_map[i] == max_count:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.busiestServers(k=3, arrival=[1, 2, 3, 4, 8, 9, 10], load=[5, 2, 10, 3, 1, 2, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n, arr):\n",
    "        self.d= [0] * (4 * n + 5)\n",
    "        self.tag = [0] * (4 * n + 5) \n",
    "        self.build(1, n, 1, arr)\n",
    "        \n",
    "    def build(self, l, r, p, arr):\n",
    "        if l == r:\n",
    "            self.d[p] = arr[l-1]\n",
    "            return \n",
    "        else:\n",
    "            mid = (l + r) >> 1\n",
    "            self.build(l, mid, 2 * p, arr)\n",
    "            self.build(mid+1, r, 2 * p + 1, arr) \n",
    "            self.d[p] = min(self.d[2*p], self.d[2*p+1])\n",
    "    \n",
    "    def putdown(self, l, r, p):\n",
    "        mid = (l + r) >> 1\n",
    "        self.d[2 * p] = self.tag[p]\n",
    "        self.d[2*p+1] = self.tag[p]\n",
    "        self.tag[2 * p] = self.tag[p]\n",
    "        self.tag[2 * p + 1] = self.tag[p]\n",
    "        self.tag[p] = 0 \n",
    "    \n",
    "    def query(self, l, r, p, x, y, val):\n",
    "        \n",
    "        if l == r:\n",
    "            return l \n",
    "        else:\n",
    "            mid = (l + r) >> 1 \n",
    "            if self.tag[p]:\n",
    "                self.putdown(l, r, p) \n",
    "            idx1, idx2= -1, -1 \n",
    "            if x <= mid and self.d[2*p] <=val:\n",
    "                idx1 = self.query(l, mid, 2 * p, x, y, val) \n",
    "                if idx1 > 0:\n",
    "                    return idx1\n",
    "            if y >= mid +1 and self.d[2 * p + 1] <= val:\n",
    "                idx2 = self.query(mid+1, r, 2 * p + 1, x, y,val) \n",
    "                if idx2 > 0:\n",
    "                    return idx2\n",
    "            return -1 \n",
    "\n",
    "    def update(self, l, r, p,c, x, y):\n",
    "        if x <= l and r <= y:\n",
    "            self.d[p] = c \n",
    "            self.tag[p] = c \n",
    "        else:\n",
    "            mid = (l + r) >> 1 \n",
    "            if self.tag[p]:\n",
    "                self.putdown(l, r, p) \n",
    "            if x <= mid:\n",
    "                self.update(l, mid, 2 * p, c , x, y) \n",
    "            if y >= mid +1:\n",
    "                self.update(mid+1, r, 2 * p + 1, c, x, y) \n",
    "            self.d[p] = min(self.d[2*p], self.d[2*p+1])\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        arr = [0] * k \n",
    "        bt = BIT(k, arr) \n",
    "        cnt = Counter()\n",
    "        for i, v in enumerate(arrival):\n",
    "            l1, r1= (i % k) + 1, k \n",
    "            if l1 <= r1:\n",
    "                idx1 = bt.query(1, k, 1, l1, r1, v)\n",
    "                #print(i, v, idx1, l1, r1) \n",
    "                if idx1 >= 0:\n",
    "                    cnt[idx1] += 1\n",
    "                    bt.update(1, k, 1, v + load[i], idx1, idx1)\n",
    "                    #arr[idx1] = v + load[i] \n",
    "                    continue \n",
    "            l2, r2 = 1, i % k \n",
    "            if l2 <= r2:\n",
    "                idx2 = bt.query(1, k, 1, l2, r2, v) \n",
    "                if idx2 >= 0:\n",
    "                    cnt[idx2] += 1\n",
    "                    bt.update(1,k, 1, v + load[i], idx2, idx2)\n",
    "                    #arr[idx2] = v + load[i] \n",
    "        arr = []\n",
    "        mx = 0 \n",
    "        for x, y in cnt.items():\n",
    "            if mx < y:\n",
    "                mx = y \n",
    "                arr = [x-1]\n",
    "            elif mx == y:\n",
    "                arr.append(x-1) \n",
    "        return arr "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n",
    "        count_list = [0] * k\n",
    "        idle_list = SortedList(range(k))\n",
    "        busy_list = []\n",
    "        for i in range(len(arrival)):\n",
    "            arrive = arrival[i]\n",
    "            while busy_list and busy_list[0][0] <= arrive:\n",
    "                _, index = heappop(busy_list)\n",
    "                idle_list.add(index)\n",
    "            if len(idle_list) == 0:\n",
    "                continue\n",
    "            need_index = i % k\n",
    "            if need_index > idle_list[-1]:\n",
    "                pop_index = 0\n",
    "            else:\n",
    "                pop_index = idle_list.bisect_left(need_index)\n",
    "            index = idle_list.pop(pop_index)\n",
    "            count_list[index] += 1\n",
    "            heappush(busy_list, [arrive + load[i], index])\n",
    "        max_count = max(count_list)\n",
    "        return [i for i, count in enumerate(count_list) if count == max_count]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
